package com.example.demo.leetcode.classics150;

/**
 * ******************************************************
 *
 *
 * 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
 *
 * 实现词典类 WordDictionary ：
 *
 * WordDictionary() 初始化词典对象
 * void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
 * bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；
 * 否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
 *
 *
 * 示例：
 *
 * 输入：
 * ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
 * [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
 * 输出：
 * [null,null,null,null,false,true,true,true]
 *
 * 解释：
 * WordDictionary wordDictionary = new WordDictionary();
 * wordDictionary.addWord("bad");
 * wordDictionary.addWord("dad");
 * wordDictionary.addWord("mad");
 * wordDictionary.search("pad"); // 返回 False
 * wordDictionary.search("bad"); // 返回 True
 * wordDictionary.search(".ad"); // 返回 True
 * wordDictionary.search("b.."); // 返回 True
 *
 *
 * 提示：
 *
 * 1 <= word.length <= 25
 * addWord 中的 word 由小写英文字母组成
 * search 中的 word 由 '.' 或小写英文字母组成
 * 最多调用 104 次 addWord 和 search
 *
 *
 *
 *
 *
 *
 * @author liugh9
 * @version 1.0
 * @classname _99添加与搜索单词数据结构设计
 * @description
 * @date 2023/08/09 14:57
 * <p>
 * ******************************************************
 */
public class _99添加与搜索单词数据结构设计 {

    class TrieNode {
        // 单词结尾
        boolean val;
        // 该层下层的26中情况
        TrieNode[] children = new TrieNode[26];
    }

    private TrieNode root;

    public _99添加与搜索单词数据结构设计() {
        root = new TrieNode();
    }

    public void addWord(String word) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            if (p.children[c - 'a'] == null) p.children[c -'a'] = new TrieNode();
            p = p.children[c -'a'];
        }
        p.val = true;
    }

    boolean search = false;
    public boolean search(String word) {
        search = false;
        TrieNode p = root;
        search(p, word);
        return search;
    }

    private void search(TrieNode p, String word) {
        if (search || p == null) return;
        if (word == null || word.length() == 0) {
            search = p.val;
            return;
        }
        char c = word.charAt(0);
        if (c != '.') {
            if (p.children[c - 'a'] != null) {
                search(p.children[c - 'a'], word.substring(1));
            }
        } else {
            for (TrieNode child : p.children) {
                if (child != null) {
                    search(child, word.substring(1));
                }
            }
        }
    }
}
